package DynamicProgramming;

public class p5最长回文子串 {
    /** dp[i][j] 表示以 i 和 j 结尾的子串是不是回文子串
     状态转移：
     i 和 j下标对应的字符相等时，
     j == i || j - i == 1, ans = ans + charAt(j);dp[i][j] = true;
     j - i > 1, if(dp[i + 1][j - 1] == true){
     ans = charAt(i) + ans + charAt(j);
     dp[i][j] = true;
     }
     遍历顺序：
     从下到上，从左到右遍历，保证dp[i + 1][j - 1]都是经过计算的
     */
    class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            boolean[][] dp = new boolean[len][len];
            int maxlenth = 0;
            int left = 0;
            int right = 0;
            for(int i = len - 1; i >= 0; i--){
                for(int j = i; j < len; j++){
                    if(s.charAt(i) == s.charAt(j)){
                        if(j == i || j - i == 1){
                            dp[i][j] = true;
                        }
                        else if(dp[i + 1][j - 1]){
                            dp[i][j] = true;
                        }
                    }
                    // i j 区间内为回文子串，且取最大的回文子串
                    if(dp[i][j] && j - i + 1 > maxlenth){
                        maxlenth = j - i + 1;
                        left = i;
                        right = j;
                    }
                }
            }
            return s.substring(left, right + 1);
        }
    }
}
